class Solution1 {
    //回溯法
    //数位之和：结合取余和除法操作
    //优化：可将搜索方向缩减为向右或向下
public:
    int movingCount(int m, int n, int k) {
        if(0 == k) return 1;
        bool* visited = new bool[m*n];  //用以记录机器人已经到达过的格子
        memset(visited, 0, m*n);
        int count = 0;  //每当一个格子被设置为true,则计算++count;

        //机器人从[0，0]开始移动
        dfs(m, n, 0, 0, k, count, visited);

        delete[] visited;

        return count;
    }

    void dfs(int &m, int &n, int mNow, int nNow, int &k, int &count, bool* visited){
        //mNow,nNow分别为当前机器人位置的行坐标及列坐标
        //当下标越界或已访问过时，返回
        if(mNow < 0 || nNow < 0 || mNow > (m - 1) || nNow > (n - 1) || visited[mNow*n + nNow])  return;

        //数位之和大于k时,返回
        if((calculate(mNow) + calculate(nNow)) > k)  return;

        //该方格可以被访问
        visited[mNow*n + nNow] = true;
        ++count;

        //递归
        dfs(m, n, mNow + 1, nNow, k, count, visited);
        dfs(m, n, mNow, nNow + 1, k, count, visited);

        return;
    }

    int calculate(int num){
        //计算数位之和并返回计算结果
        int allPlus = 0;
        while(num){
            allPlus += (num % 10);
            num /= 10;
        }
        return allPlus;
    }
};

/************************************************************************************/
class Solution2 {
    //递推：只要左边或者上边任一个格子是能到达的，直接可以递推当前格子也是可以到达的
    //若数位之和不满足条件。直接跳过
    //时间复杂度和空间复杂度O(mn)
public:
    int movingCount(int m, int n, int k) {
        if(0 == k) return 1;
        vector<vector<bool>>visited(m, vector<bool>(n, false));  //记录是否可到达的矩阵
        visited[0][0] = true;  //起始位置
        int count = 1;

        //机器人从[0，0]开始移动
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if((i == 0 && j ==0) || ((calculate(i) + calculate(j)) > k))  continue;
                if(i >= 1)  visited[i][j] = visited[i][j] + visited[i - 1][j];
                if(j >= 1)  visited[i][j] = visited[i][j] + visited[i][j - 1];

                count += visited[i][j];
            }
        }

        return count;
    }

    int calculate(int num){
        //计算数位之和并返回计算结果
        int allPlus = 0;
        while(num){
            allPlus += (num % 10);
            num /= 10;
        }
        return allPlus;
    }
};